{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #烹饪料理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #backtracking #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #回溯 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: perfectMenu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #烹饪料理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "欢迎各位勇者来到力扣城，城内设有烹饪锅供勇者制作料理，为自己恢复状态。\n",
    "\n",
    "勇者背包内共有编号为 `0 ~ 4` 的五种食材，其中 `materials[j]` 表示第 `j` 种食材的数量。通过这些食材可以制作若干料理，`cookbooks[i][j]` 表示制作第 `i` 种料理需要第 `j` 种食材的数量，而 `attribute[i] = [x,y]` 表示第 `i` 道料理的美味度 `x` 和饱腹感 `y`。\n",
    "\n",
    "在饱腹感不小于 `limit` 的情况下，请返回勇者可获得的最大美味度。如果无法满足饱腹感要求，则返回 `-1`。\n",
    "\n",
    "**注意：**\n",
    "- 每种料理只能制作一次。\n",
    "\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`materials = [3,2,4,1,2]`\n",
    ">`cookbooks = [[1,1,0,1,2],[2,1,4,0,0],[3,2,4,1,0]]`\n",
    ">`attribute = [[3,2],[2,4],[7,6]]`\n",
    ">`limit = 5`\n",
    ">\n",
    ">输出：`7`\n",
    ">\n",
    ">解释：\n",
    ">食材数量可以满足以下两种方案：\n",
    ">方案一：制作料理 0 和料理 1，可获得饱腹感 2+4、美味度 3+2\n",
    ">方案二：仅制作料理 2， 可饱腹感为 6、美味度为 7\n",
    ">因此在满足饱腹感的要求下，可获得最高美味度 7\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`materials = [10,10,10,10,10]`\n",
    ">`cookbooks = [[1,1,1,1,1],[3,3,3,3,3],[10,10,10,10,10]]`\n",
    ">`attribute = [[5,5],[6,6],[10,10]]`\n",
    ">`limit = 1`\n",
    ">\n",
    ">输出：`11`\n",
    ">\n",
    ">解释：通过制作料理 0 和 1，可满足饱腹感，并获得最高美味度 11\n",
    "\n",
    "**提示：**\n",
    "+ `materials.length == 5`\n",
    "+ `1 <= cookbooks.length == attribute.length <= 8`\n",
    "+ `cookbooks[i].length == 5`\n",
    "+ `attribute[i].length == 2`\n",
    "+ `0 <= materials[i], cookbooks[i][j], attribute[i][j] <= 20`\n",
    "+ `1 <= limit <= 100`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [UEcfPD](https://leetcode.cn/problems/UEcfPD/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [UEcfPD](https://leetcode.cn/problems/UEcfPD/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,4,1,2]\\n[[1,1,0,1,2],[2,1,4,0,0],[3,2,4,1,0]]\\n[[3,2],[2,4],[7,6]]\\n5', '[10,10,10,10,10]\\n[[1,1,1,1,1],[3,3,3,3,3],[10,10,10,10,10]]\\n[[5,5],[6,6],[10,10]]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        ls = len(cookbooks)\n",
    "        bi = 2 ** ls\n",
    "\n",
    "        ans = -1\n",
    "\n",
    "        # 每一种方案\n",
    "        for b in range(bi):\n",
    "            m = materials[::]\n",
    "            flag = False\n",
    "            x = y = 0\n",
    "            # 每一个料理\n",
    "            for i in range(ls):\n",
    "                if (1 << i) & b:\n",
    "                    # 每一种食材\n",
    "                    for j in range(5):\n",
    "                        if m[j] < cookbooks[i][j]:\n",
    "                            flag = True\n",
    "                            break\n",
    "                        m[j] -= cookbooks[i][j]\n",
    "                    x += attribute[i][0]\n",
    "                    y += attribute[i][1]\n",
    "                \n",
    "                if flag:\n",
    "                    break\n",
    "            # print(bin(b), flag, x, y)\n",
    "            if not flag and y >= limit:\n",
    "                ans = max(ans, x)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        # 1 <= cookbooks.length == attribute.length <= 8, 每种料理只能制作一次。\n",
    "        n=len(cookbooks)\n",
    "        ans=-1\n",
    "        for i in range(1<<n):\n",
    "            cook=[0]*5\n",
    "            attr=[0,0]\n",
    "            for j in range(n):\n",
    "                if i & (1<<j):\n",
    "                    # 方案i需要做cook[j],获得属性attr[j]\n",
    "                    for k in range(5):\n",
    "                        cook[k]+=cookbooks[j][k]\n",
    "                    attr[0]+=attribute[j][0]\n",
    "                    attr[1]+=attribute[j][1]\n",
    "            # 状态总结sum\n",
    "            for k in range(5):\n",
    "                if cook[k]>materials[k]:\n",
    "                    break\n",
    "            else:\n",
    "                if attr[1]>=limit:\n",
    "                    ans=max(ans,attr[0])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        # 如果每道菜的饱腹感总和都小于limit，直接返回-1\n",
    "        baofu = 0\n",
    "        for i in attribute:\n",
    "            baofu += i[0]\n",
    "        if baofu < limit:\n",
    "            return -1\n",
    "        \n",
    "        # 枚举\n",
    "        n = len(cookbooks)\n",
    "        cur_cook = []\n",
    "        x = 2**n\n",
    "        \n",
    "        meiwei_list = []\n",
    "        for i in range(x):\n",
    "            cur_baofu = 0\n",
    "            cur_matirals = [0] * 5\n",
    "            cur_meiwei = 0\n",
    "            bin_num = list(bin(i))[2:]\n",
    "            delta = n - len(bin_num)\n",
    "            cur_cook = [0] * delta\n",
    "            for j in bin_num:\n",
    "                cur_cook.append(int(j))\n",
    "            for k in range(len(cur_cook)):\n",
    "                if cur_cook[k] == 1:\n",
    "                    cur_baofu += attribute[k][1]\n",
    "                    cur_matirals = list(map(add,cur_matirals,cookbooks[k]))\n",
    "                    cur_meiwei += attribute[k][0]\n",
    "            if cur_baofu >= limit:\n",
    "                can_cook = True               \n",
    "                for ii in range(len(materials)):\n",
    "                    if materials[ii] < cur_matirals[ii]:\n",
    "                        can_cook = False\n",
    "                        break\n",
    "                if can_cook:\n",
    "                    meiwei_list.append(cur_meiwei)\n",
    "            else:\n",
    "                continue\n",
    "        if len(meiwei_list) == 0:\n",
    "            return -1\n",
    "        return max(meiwei_list)\n",
    "\n",
    "            \n",
    "\n",
    "                    \n",
    "                    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]],\n",
    "                    limit: int) -> int:\n",
    "        n = len(cookbooks)\n",
    "        res = -1\n",
    "        for i in range(1, 1 << n):\n",
    "            s = [0] * 5\n",
    "            tasty = 0\n",
    "            energy = 0\n",
    "            for j in range(n):\n",
    "                if (i & (1 << j)) != 0:\n",
    "                    s = [si + mi for si, mi in zip(s, cookbooks[j])]\n",
    "                    tasty += attribute[j][0]\n",
    "                    energy += attribute[j][1]\n",
    "            if energy >= limit and all(si <= mi for si, mi in zip(s, materials)):\n",
    "                res = max(res, tasty)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(\n",
    "        self, \n",
    "        materials: List[int], \n",
    "        cookbooks: List[List[int]], \n",
    "        attribute: List[List[int]], \n",
    "        limit: int\n",
    "    ) -> int:\n",
    "\n",
    "        m, n = len(materials), len(cookbooks)\n",
    "\n",
    "        def dfs(i: int) -> None:\n",
    "            nonlocal res, x, y, needs\n",
    "\n",
    "            if i == n:\n",
    "                if y >= limit:\n",
    "                    res = max(res, x)\n",
    "                return\n",
    "\n",
    "            dfs(i + 1)\n",
    "\n",
    "            for j in range(m):\n",
    "                needs[j] += cookbooks[i][j]\n",
    "                if needs[j] > materials[j]:\n",
    "                    for k in range(j + 1):\n",
    "                        needs[k] -= cookbooks[i][k]\n",
    "                    return\n",
    "\n",
    "            x += attribute[i][0]\n",
    "            y += attribute[i][1]\n",
    "\n",
    "            dfs(i + 1)\n",
    "\n",
    "            for j in range(m):\n",
    "                needs[j] -= cookbooks[i][j]\n",
    "\n",
    "            x -= attribute[i][0]\n",
    "            y -= attribute[i][1]\n",
    "\n",
    "        res = -1\n",
    "        # x: 美味度\n",
    "        # y: 饱腹感\n",
    "        x, y = 0, 0\n",
    "        \n",
    "        needs = [0] * m\n",
    "\n",
    "        dfs(0) \n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        n=len(cookbooks)\n",
    "        target=-1\n",
    "        for i in range(1,1<<n):#所有可能的料理方案:\n",
    "            hungry=0\n",
    "            delicous=0\n",
    "            s=materials\n",
    "            for j in range(0,n):\n",
    "                if i&(1<<j)!=0:#判断i方案有没有j这个料理\n",
    "                    hungry+=attribute[j][1]\n",
    "                    delicous+=attribute[j][0]\n",
    "                    s=[x-y for x,y in zip(s,cookbooks[j])]#记录一下材料剩余数量\n",
    "            if hungry>=limit and min(s)>=0:\n",
    "                target=max(delicous,target)\n",
    "        return target\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        # 回溯法 组合问题\n",
    "\n",
    "        ans = -1\n",
    "        def backward(materials, used, a1, a2, startIndex):\n",
    "            nonlocal ans\n",
    "            if a2 >= limit:\n",
    "                ans = max(ans, a1)\n",
    "            for i in range(startIndex, len(cookbooks)):\n",
    "                if used[i] == False:\n",
    "                    flag = True\n",
    "                    for j in range(5):\n",
    "                        if materials[j] < cookbooks[i][j]:\n",
    "                            flag = False\n",
    "                            break\n",
    "                    if flag == True:\n",
    "                        for j in range(5):\n",
    "                            materials[j] -= cookbooks[i][j]\n",
    "                        used[i] = True\n",
    "                        backward(materials, used, a1+attribute[i][0], a2+attribute[i][1], i+1)\n",
    "                        used[i] = False\n",
    "                        for j in range(5):\n",
    "                            materials[j] += cookbooks[i][j]\n",
    "            \n",
    "        backward(materials, [False for _ in range(len(cookbooks))], 0, 0, 0)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]],\n",
    "                    limit: int) -> int:\n",
    "        n = len(cookbooks)\n",
    "        res = -1\n",
    "        for i in range(1, 1 << n):\n",
    "            s = [0] * 5\n",
    "            tasty = 0\n",
    "            energy = 0\n",
    "            for j in range(n):\n",
    "                if (i & (1 << j)) != 0:\n",
    "                    s = [si + mi for si, mi in zip(s, cookbooks[j])]\n",
    "                    tasty += attribute[j][0]\n",
    "                    energy += attribute[j][1]\n",
    "            if energy >= limit and all(si <= mi for si, mi in zip(s, materials)):\n",
    "                res = max(res, tasty)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        global final\n",
    "        final = -1\n",
    "        def dfs(leave, need, curDelicious, p):\n",
    "            global final\n",
    "            if need <= 0:\n",
    "                if final < curDelicious:\n",
    "                    final = curDelicious\n",
    "\n",
    "            for i in range(p, len(cookbooks)):\n",
    "                success = True\n",
    "                temp = [0] * len(materials)\n",
    "                for j in range(len(materials)):\n",
    "                    temp[j] = leave[j] - cookbooks[i][j]\n",
    "                    if temp[j] >= 0:\n",
    "                        continue\n",
    "                    else:\n",
    "                        success = False\n",
    "                        break\n",
    "                # 第i种食谱可以做，那么就先做，做完后再去做其他食谱\n",
    "                if success:\n",
    "                    dfs(temp, need - attribute[i][-1], curDelicious + attribute[i][0], i+1)\n",
    "                # 还要遍历不做这种食谱的情况\n",
    "                else:\n",
    "                    dfs(leave, need, curDelicious, i+1)\n",
    "\n",
    "        dfs(materials, limit, 0, 0)\n",
    "        return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        global final\n",
    "        final = -1\n",
    "        def dfs(materials,cookbooks, attribute, leave, need, curDelicious, p):\n",
    "            global final\n",
    "            if need <= 0:\n",
    "                if final < curDelicious:\n",
    "                    final = curDelicious\n",
    "\n",
    "            for i in range(p, len(cookbooks)):\n",
    "                success = True\n",
    "                temp = [0] * len(materials)\n",
    "                for j in range(len(materials)):\n",
    "                    temp[j] = leave[j] - cookbooks[i][j]\n",
    "                    if temp[j] >= 0:\n",
    "                        continue\n",
    "                    else:\n",
    "                        success = False\n",
    "                        break\n",
    "                # 第i种食谱可以做，那么就先做，做完后再去做其他食谱\n",
    "                if success:\n",
    "                    dfs(materials, cookbooks, attribute, temp, need - attribute[i][-1], curDelicious + attribute[i][0], i+1)\n",
    "                # 还要遍历不做这种食谱的情况\n",
    "                else:\n",
    "                    dfs(materials, cookbooks, attribute, leave, need, curDelicious, i+1)\n",
    "\n",
    "        dfs(materials, cookbooks, attribute, materials, limit, 0, 0)\n",
    "        return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        n = len(cookbooks)\n",
    "        maxdel = self.f(cookbooks,materials,0,n,limit,0,0,attribute)\n",
    "        return maxdel\n",
    "\n",
    "    def f(self,cookbooks,materials,make,n,limit,hungry,deli,attribute):\n",
    "        if make >= n:\n",
    "            if hungry>=limit:\n",
    "                return deli\n",
    "            else:\n",
    "                return -1\n",
    "        else:\n",
    "            if not self.canmake(cookbooks[make],materials):\n",
    "                return self.f(cookbooks,materials.copy(),make+1,n,limit,hungry,deli,attribute)\n",
    "            else:\n",
    "                max1 = self.f(cookbooks,materials.copy(),make+1,n,limit,hungry,deli,attribute)\n",
    "                newmaterials = []\n",
    "                for i in range(len(materials)):\n",
    "                    newmaterials.append(materials[i] - cookbooks[make][i])\n",
    "                hungry += attribute[make][1]\n",
    "                deli += attribute[make][0]\n",
    "                #print(deli)\n",
    "                max2 = self.f(cookbooks,newmaterials,make+1,n,limit,hungry,deli,attribute)\n",
    "                maxdel = max(max1,max2)\n",
    "                return maxdel\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def canmake(self,cookbook,materials):\n",
    "        for i in range(len(cookbook)):\n",
    "            if cookbook[i] > materials[i]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        n=len(cookbooks)\n",
    "        ans=-1\n",
    "        for i in range(1<<n):\n",
    "            cook=[0]*5\n",
    "            attr=[0,0]\n",
    "            for j in range(n):\n",
    "                if i & (1<<j):\n",
    "                    # 方案i需要做cook[j],获得属性attr[j]\n",
    "                    for k in range(5):\n",
    "                        cook[k]+=cookbooks[j][k]\n",
    "                    attr[0]+=attribute[j][0]\n",
    "                    attr[1]+=attribute[j][1]\n",
    "            # 状态总结sum\n",
    "            for k in range(5):\n",
    "                if cook[k]>materials[k]:\n",
    "                    break\n",
    "            else:\n",
    "                if attr[1]>=limit:\n",
    "                    ans=max(ans,attr[0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ans = -1\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        global ans\n",
    "        ans = -1\n",
    "        n = len(materials)\n",
    "        m = len(cookbooks)\n",
    "        def dfs(loc, lhd, rhd):\n",
    "            if loc >= m:\n",
    "                return\n",
    "            mk = 1\n",
    "            for i in range(n):\n",
    "                materials[i] -= cookbooks[loc][i]\n",
    "                if materials[i] < 0:\n",
    "                    mk = 0\n",
    "            if mk:\n",
    "                tmp = lhd + attribute[loc][1]\n",
    "                tans = rhd + attribute[loc][0]\n",
    "                global ans\n",
    "                if tmp>=limit and tans > ans:\n",
    "                    ans = tans\n",
    "                dfs(loc +1,tmp,tans)\n",
    "            for i in range(n):\n",
    "                materials[i] += cookbooks[loc][i]\n",
    "            dfs(loc+1, lhd, rhd)\n",
    "        dfs(0,0,0)\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtracking(self,materials,cookbooks,attribute,hunger,spiritual,limit,startIndex):\n",
    "        temp=True#是否返回结果\n",
    "        for x in range(startIndex,len(cookbooks)):\n",
    "            for y in range(5):\n",
    "                if materials[y]<cookbooks[x][y]:\n",
    "                    break\n",
    "            if y==4 and materials[y]>=cookbooks[x][y]:\n",
    "                temp=False\n",
    "            if not temp:\n",
    "                break\n",
    "\n",
    "\n",
    "        if startIndex==len(cookbooks) or temp:\n",
    "            if hunger>=limit:\n",
    "                self.maxspiritual=max(self.maxspiritual,spiritual)\n",
    "            return\n",
    "        \n",
    "        for i in range(startIndex,len(cookbooks)):\n",
    "            for j in range(5):\n",
    "                if materials[j]<cookbooks[i][j]:\n",
    "                    break\n",
    "            if j==4 and materials[j]>=cookbooks[i][j]:\n",
    "                materials=[materials[j]-cookbooks[i][j] for j in range(5)]\n",
    "                self.backtracking(materials,cookbooks,attribute,hunger+attribute[i][1],spiritual+attribute[i][0],limit,i+1)\n",
    "                materials=[materials[j]+cookbooks[i][j] for j in range(5)]\n",
    "\n",
    "\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        self.maxspiritual=0\n",
    "        self.backtracking(materials,cookbooks,attribute,0,0,limit,0)\n",
    "        return self.maxspiritual if self.maxspiritual!=0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        n = len(cookbooks)\n",
    "        res = set()\n",
    "        self.ans = -1\n",
    "        def dfs(nums,li,visited):\n",
    "            v = tuple(visited)\n",
    "            if v not in res:\n",
    "                x,y = 0,0\n",
    "                for k in v:\n",
    "                    x += attribute[k][0]\n",
    "                    y += attribute[k][1]\n",
    "                if y >= limit:\n",
    "                    self.ans = max(self.ans,x)\n",
    "                res.add(v)\n",
    "            for i in range(n):\n",
    "                #print(f'当前余额{nums} 当前制作列表{li} 选择方法{i}')\n",
    "                if i in visited:\n",
    "                    #print(f'方法{i} 已经使用过,回退')\n",
    "                    continue\n",
    "                data = True\n",
    "                for j in range(5):\n",
    "                    if nums[j] < cookbooks[i][j]:\n",
    "                        data = False\n",
    "                    nums[j] -= cookbooks[i][j]\n",
    "                #print(f'余额{nums} 选择制作配方{i,cookbooks[i]} 制作后剩余{nums}的钱')\n",
    "                if data:\n",
    "                    \n",
    "                    li.append(i)\n",
    "                    visited.add(i)\n",
    "                    #print(f'开始制作 当前余额{nums} 当前制作列表{li} 选择方法{i}')\n",
    "                    dfs(nums,li,visited)\n",
    "                    li.pop()\n",
    "                    visited.remove(i)\n",
    "                for j in range(5):\n",
    "                    nums[j] += cookbooks[i][j]\n",
    "                    #print(f'增加 {cookbooks[i][j]}的钱')\n",
    "                #print(f'回溯 {nums},{li},{visited}')\n",
    "               \n",
    "        dfs(materials,[],set())\n",
    "        #print(res)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        selected = list()\n",
    "        ans = 0\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x,y):\n",
    "            nonlocal selected,ans,materials\n",
    "            for dish in cookbooks:\n",
    "                lack = False\n",
    "                i = cookbooks.index(dish)\n",
    "                if i in selected:\n",
    "                    continue\n",
    "                restmaterials = []\n",
    "                for j in range(5):\n",
    "                    if materials[j]-dish[j]>=0:\n",
    "                        restmaterials.append(materials[j]-dish[j])\n",
    "                    else:\n",
    "                        lack = True\n",
    "                        break\n",
    "                if lack:\n",
    "                    continue\n",
    "                else:\n",
    "                    selected.append(i)\n",
    "                    materials1 = materials\n",
    "                    materials = restmaterials\n",
    "                    dfs(x+attribute[i][0],y+attribute[i][1])\n",
    "                    materials = materials1\n",
    "                    selected.pop()\n",
    "            \n",
    "            if y>=limit:\n",
    "                ans = max(x,ans)\n",
    "            return \n",
    "        \n",
    "        dfs(0,0)\n",
    "        return ans if ans else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        def f(i,x,y,m):\n",
    "            if i == n:\n",
    "                if y>=limit:\n",
    "                    res.append(x)\n",
    "                return\n",
    "            \n",
    "            pick=True\n",
    "            for a,b in zip(m,cookbooks[i]):\n",
    "                if a<b:\n",
    "                    pick=False\n",
    "                    break\n",
    "            \n",
    "            if pick:\n",
    "                f(i+1,x+attribute[i][0],y+attribute[i][1],[a-b for a,b in zip(m,cookbooks[i])])\n",
    "            f(i+1,x,y,m)\n",
    "        \n",
    "        res=[-1]\n",
    "        n=len(cookbooks)\n",
    "        f(0,0,0,materials)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        n = len(cookbooks)\n",
    "        bits = [0] * 8\n",
    "        max_taste = -1\n",
    "        for i in range(1, 2**n):\n",
    "            temp = i\n",
    "            for j in range(8):\n",
    "                bits[j] = temp % 2\n",
    "                temp //= 2\n",
    "            temp_material = [0] * 5\n",
    "            temp_x = 0\n",
    "            temp_y = 0\n",
    "            for j in range(n):\n",
    "                if bits[j] == 1:\n",
    "                    for k in range(5):\n",
    "                        temp_material[k] += cookbooks[j][k]\n",
    "                    temp_x += attribute[j][0]\n",
    "                    temp_y += attribute[j][1]\n",
    "            valid = temp_y >= limit\n",
    "            if valid:\n",
    "                for j in range(5):\n",
    "                    if temp_material[j] > materials[j]:\n",
    "                        valid = False\n",
    "            if valid:\n",
    "                max_taste = max(max_taste, temp_x)\n",
    "        return max_taste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        mark=[False for _ in range(len(cookbooks))]\n",
    "        ans=-1\n",
    "        def dfs(temp_att, temp_limit):\n",
    "            nonlocal ans\n",
    "            if temp_limit>=limit:\n",
    "                ans=max(ans, temp_att)\n",
    "            n=len(cookbooks)\n",
    "            for i in range(n):\n",
    "                if mark[i]==True:\n",
    "                    continue\n",
    "                need=cookbooks[i]\n",
    "                can=True\n",
    "                for j in range(len(materials)):\n",
    "                    if materials[j]<need[j]:\n",
    "                        can=False\n",
    "                        break\n",
    "                if can:\n",
    "                    for j in range(len(materials)):\n",
    "                        materials[j]-=need[j]\n",
    "                    mark[i]=True\n",
    "                    dfs(temp_att+attribute[i][0], attribute[i][1]+temp_limit)\n",
    "                    mark[i]=False\n",
    "                    for j in range(len(materials)):\n",
    "                        materials[j]+=need[j]\n",
    "        dfs(0,0)\n",
    "        return ans\n",
    "                            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(\n",
    "        self, \n",
    "        materials: List[int], \n",
    "        cookbooks: List[List[int]], \n",
    "        attribute: List[List[int]], \n",
    "        limit: int\n",
    "    ) -> int:\n",
    "\n",
    "        m, n = len(materials), len(cookbooks)\n",
    "\n",
    "        res = -1\n",
    "\n",
    "        # 枚举料理子集\n",
    "        for mask in range(1, 1 << n):\n",
    "            cooks = []\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i):\n",
    "                    cooks.append(i)\n",
    "\n",
    "            needs = [0] * m\n",
    "            x, y = 0, 0 # x: 美味度，y: 饱腹感\n",
    "\n",
    "            for i in cooks:\n",
    "                x += attribute[i][0]\n",
    "                y += attribute[i][1]\n",
    "                for j in range(m):\n",
    "                    needs[j] += cookbooks[i][j]\n",
    "\n",
    "            if y < limit:\n",
    "                continue\n",
    "\n",
    "            for a, b in zip(materials, needs):\n",
    "                if a < b:\n",
    "                    break\n",
    "            else:\n",
    "                res = max(res, x)\n",
    "\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        result, n = -1, len(cookbooks)\n",
    "        def recur(st, l, x=0):\n",
    "            for i in range(st, n):\n",
    "                if all(materials[j] >= cookbooks[i][j] for j in range(5)):\n",
    "                    for j in range(5):\n",
    "                        materials[j] -= cookbooks[i][j]\n",
    "                    recur(i+1, l-attribute[i][1], x+attribute[i][0])\n",
    "                    for j in range(5):\n",
    "                        materials[j] += cookbooks[i][j]\n",
    "            if l <= 0:\n",
    "                nonlocal result\n",
    "                result = max(result, x)\n",
    "        return recur(0, limit) or result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        n_cook = len(cookbooks)\n",
    "        v_mwd_max = 0\n",
    "        for i_menu in range(1, 1 << n_cook):\n",
    "            # print(bin(i_menu))\n",
    "            materials_tmp = materials[:]\n",
    "            flag_break = 0\n",
    "            v_bfg = 0\n",
    "            v_mwd = 0\n",
    "            for i_cook in range(n_cook):\n",
    "                if i_menu & (1 << i_cook):\n",
    "                    # print('now cook {}'.format(i_cook))\n",
    "                    for i_material in range(len(materials)):\n",
    "                        materials_tmp[i_material] -= cookbooks[i_cook][i_material]\n",
    "                        if materials_tmp[i_material] < 0:\n",
    "                            flag_break = 1\n",
    "                            break\n",
    "                    if flag_break == 1:\n",
    "                        break\n",
    "                    v_mwd += attribute[i_cook][0]\n",
    "                    v_bfg += attribute[i_cook][1]\n",
    "            if v_bfg >= limit and v_mwd > v_mwd_max:\n",
    "                v_mwd_max = v_mwd\n",
    "        return v_mwd_max if v_mwd_max > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        coun=-1\n",
    "        l1=len(cookbooks)\n",
    "        l2=len(materials)\n",
    "        for i in range(2**l1):\n",
    "            k=0\n",
    "            p=list(materials)\n",
    "            full=0\n",
    "            taste=0\n",
    "            t=bin(i)[2:].zfill(l1)\n",
    "            for x in range(l1):\n",
    "                if int(t[x])==1:\n",
    "                    full+=attribute[x][1]\n",
    "                    taste+=attribute[x][0]\n",
    "                    for j in range(l2):\n",
    "                        if not cookbooks[x][j]>p[j]:\n",
    "                            p[j]-=cookbooks[x][j]\n",
    "                        else:\n",
    "                            k=1\n",
    "                            break\n",
    "                    if k==1:\n",
    "                        break\n",
    "            if full>=limit and k!=1:\n",
    "                coun=max(coun,taste)\n",
    "        return coun\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        n=len(cookbooks)\n",
    "        ans=-1\n",
    "        for i in range(1<<n):\n",
    "            cook=[0]*5\n",
    "            attr=[0,0]\n",
    "            for j in range(n):\n",
    "                if i & (1<<j):\n",
    "                    # 方案i需要做cook[j],获得属性attr[j]\n",
    "                    for k in range(5):\n",
    "                        cook[k]+=cookbooks[j][k]\n",
    "                    attr[0]+=attribute[j][0]\n",
    "                    attr[1]+=attribute[j][1]\n",
    "            # 状态总结sum\n",
    "            for k in range(5):\n",
    "                if cook[k]>materials[k]:\n",
    "                    break\n",
    "            else:\n",
    "                if attr[1]>=limit:\n",
    "                    ans=max(ans,attr[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        n = len(cookbooks) \n",
    "        ans = -1\n",
    "        for i in range(1 << n):\n",
    "            cook = [0] * 5\n",
    "            attr = [0, 0]\n",
    "            for j in range(n):\n",
    "                if i & (1 << j):\n",
    "                    for k in range(5):\n",
    "                        cook[k] += cookbooks[j][k]\n",
    "                    attr[0] += attribute[j][0]\n",
    "                    attr[1] += attribute[j][1]\n",
    "            for k in range(5):\n",
    "                if cook[k] > materials[k]:\n",
    "                    break\n",
    "            else:\n",
    "                if attr[1] >= limit:\n",
    "                    ans = max(ans, attr[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        dp, pres, res = [[True, [0 for _ in range(7)]]], 1, -1\n",
    "        for i in range(len(attribute)):\n",
    "            for j in range(pres, pres << 1):\n",
    "                if dp[j - pres][0]:\n",
    "                    dp.append([True, []])\n",
    "                    for k in range(5):\n",
    "                        dp[-1][1].append(dp[j - pres][1][k] + cookbooks[i][k])\n",
    "                        dp[-1][0] &= dp[-1][1][k] <= materials[k]\n",
    "                    if dp[-1][0]:\n",
    "                        dp[-1][1].append(dp[j - pres][1][5] + attribute[i][0])\n",
    "                        dp[-1][1].append(dp[j - pres][1][6] + attribute[i][1])\n",
    "                        if dp[-1][1][6] >= limit:\n",
    "                            res = max(res, dp[-1][1][5])\n",
    "                else:\n",
    "                    dp.append([False])\n",
    "            pres <<= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        # 1 <= cookbooks.length == attribute.length <= 8, 每种料理只能制作一次。\n",
    "        n=len(cookbooks)\n",
    "        ans=-1\n",
    "        for i in range(1<<n):\n",
    "            cook=[0]*5\n",
    "            attr=[0,0]\n",
    "            for j in range(n):\n",
    "                if i & (1<<j): # i==2的j次方\n",
    "                    # 方案i需要做cook[j],获得属性attr[j]\n",
    "                    for k in range(5):\n",
    "                        cook[k]+=cookbooks[j][k]\n",
    "                    attr[0]+=attribute[j][0]\n",
    "                    attr[1]+=attribute[j][1]\n",
    "            # 状态总结sum\n",
    "            for k in range(5):\n",
    "                if cook[k]>materials[k]:\n",
    "                    break\n",
    "            else:\n",
    "                if attr[1]>=limit:\n",
    "                    ans=max(ans,attr[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        def has_materials(materials):\n",
    "            for material in materials:\n",
    "                if material < 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def can_cookbooks(materials, cookbook):\n",
    "            materials = [materials[i] - cookbook[i] for i in range(num_material)]\n",
    "            return materials\n",
    "        \n",
    "        def back_trace(materials, x, y, deep):\n",
    "            if y >= limit:\n",
    "                ans.append(x)\n",
    "            if deep < num_attribute:\n",
    "                back_trace(materials[:],x,y,deep + 1)\n",
    "                materials = can_cookbooks(materials, cookbooks[deep])\n",
    "                if has_materials(materials):\n",
    "                    back_trace(materials[:], x+attribute[deep][0],y+attribute[deep][1], deep + 1)\n",
    "        ans = [-1]\n",
    "        num_attribute = len(attribute)\n",
    "        num_material = len(materials)\n",
    "        back_trace(materials, 0, 0, 0)\n",
    "        return max(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        def has_materials(materials):\n",
    "            for material in materials:\n",
    "                if material < 0:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        def can_cookbooks(materials, cookbook):\n",
    "            materials = [materials[i] - cookbook[i] for i in range(num_material)]\n",
    "            return materials\n",
    "\n",
    "        \n",
    "        def back_trace(materials, x, y, deep):\n",
    "            if y >= limit:\n",
    "                    ans.append(x)\n",
    "            if deep < num_attribute:\n",
    "                back_trace(materials[:], x, y, deep + 1)\n",
    "                materials =  can_cookbooks(materials, cookbooks[deep])\n",
    "                if has_materials(materials):\n",
    "                    back_trace(materials[:], x+attribute[deep][0], y+attribute[deep][1], deep + 1)\n",
    "        ans = [-1]\n",
    "        num_attribute = len(attribute)\n",
    "        num_material = len(materials)\n",
    "        back_trace(materials, 0, 0, 0)\n",
    "        return max(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "\n",
    "        self.ret = -1\n",
    "        tmp = [0] * len(cookbooks)\n",
    "\n",
    "        def back_track(i):\n",
    "            if i == len(cookbooks):\n",
    "                cost = [0,0,0,0,0]\n",
    "                satiety = 0\n",
    "                deliciousness = 0\n",
    "                flag = True\n",
    "                for idx, meal in enumerate(tmp):\n",
    "                    if meal == 0: continue\n",
    "                    for j in range(5):\n",
    "                        cost[j] += cookbooks[idx][j]\n",
    "                        if cost[j] > materials[j]: flag = False\n",
    "                    deliciousness += attribute[idx][0]\n",
    "                    satiety += attribute[idx][1]\n",
    "                    if satiety < limit: flag = False\n",
    "                    if flag: self.ret = max(self.ret, deliciousness)\n",
    "                return\n",
    "            tmp[i] = 1\n",
    "            back_track(i+1)\n",
    "            tmp[i] = 0\n",
    "            back_track(i+1)\n",
    "\n",
    "        back_track(0)\n",
    "\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        n=len(cookbooks)\n",
    "        ans=-1\n",
    "        for i in range(1<<n):\n",
    "            cook=[0]*5\n",
    "            attr=[0,0]\n",
    "            for j in range(n):\n",
    "                if i & (1<<j):\n",
    "                    # 方案i需要做cook[j],获得属性attr[j]\n",
    "                    for k in range(5):\n",
    "                        cook[k]+=cookbooks[j][k]\n",
    "                    attr[0]+=attribute[j][0]\n",
    "                    attr[1]+=attribute[j][1]\n",
    "            # 状态总结sum\n",
    "            for k in range(5):\n",
    "                if cook[k]>materials[k]:\n",
    "                    break\n",
    "            else:\n",
    "                if attr[1]>=limit:\n",
    "                    ans=max(ans,attr[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        maxAns = -1\n",
    "        def dfs(materials, cookbooks, attribute, limit, exist, sumx, sumy):\n",
    "            nonlocal maxAns\n",
    "            if sumy >= limit: maxAns = max(maxAns, sumx)\n",
    "            length = len(cookbooks)\n",
    "            for i in range(length):\n",
    "                if exist[i]: continue\n",
    "                need = cookbooks[i]\n",
    "                can = True\n",
    "                for j, x in enumerate(need):\n",
    "                    if materials[j] < x:\n",
    "                        can = False\n",
    "                        break\n",
    "                if can:\n",
    "                    exist[i] = True\n",
    "                    for k, y in enumerate(need):\n",
    "                        materials[k] -= y\n",
    "                    dfs(materials, cookbooks, attribute, limit, exist, sumx + attribute[i][0], sumy + attribute[i][1])\n",
    "                    for k, y in enumerate(need):\n",
    "                        materials[k] += y\n",
    "                    exist[i] = True\n",
    "        dfs(materials, cookbooks, attribute, limit, [False] * len(cookbooks), 0, 0)\n",
    "        return maxAns\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "#         m,n=len(materials),len(cookbooks)\n",
    "#         # self.ans=0\n",
    "#         def getValue(material,x,su,cul):\n",
    "#             if x==n:return 0\n",
    "#             if x>0:\n",
    "#                 for i in range(m):\n",
    "#                     if cookbooks[x][i]>material[i]:\n",
    "#                         return su if cul>=limit else 0\n",
    "#                     material[i]-=cookbooks[x][i]\n",
    "#                 su+=attribute[x][0]\n",
    "#                 cul+=attribute[x][1]\n",
    "#             res=0\n",
    "#             for i in range(x,n):\n",
    "#                 res=max(res,attribute[i][0]+getValue(material,i+1,su,cul))\n",
    "#             return su+res\n",
    "#         return getValue(materials,0,0,0)\n",
    "\n",
    "# class Solution:\n",
    "#     def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "#         m,n=len(materials),len(cookbooks)\n",
    "#         # self.ans=0\n",
    "#         def getValue(material,x,su,cul):\n",
    "#             res=0\n",
    "#             for i in range(x,n):\n",
    "#                 meet=True\n",
    "#                 for i in range(m):\n",
    "#                     if cookbooks[x][i]>material[i]:\n",
    "#                         meet=False\n",
    "#                         break\n",
    "#                     material[i]-=cookbooks[x][i]\n",
    "#                 if not meet:\n",
    "#                     continue\n",
    "#                 csu,ccul=su,cul\n",
    "#                 csu+=attribute[x][0]\n",
    "#                 ccul+=+attribute[x][1]\n",
    "#                 res=max(res,attribute[x][0]+getValue(material,i+1,csu,ccul))\n",
    "#             return su+res if cul>=limit else 0\n",
    "#         return getValue(materials,0,0,0)\n",
    "\n",
    "# my：前序DFS\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        m,n=len(materials),len(cookbooks)\n",
    "        self.ans=-1 ### 全局变量更新\n",
    "        def getValue(material,x,su,cul):\n",
    "            if cul>=limit:\n",
    "                self.ans=max(self.ans,su)\n",
    "            for j in range(x,n):\n",
    "                meet=True\n",
    "                tmaterial=material[:]\n",
    "                for i in range(m):\n",
    "                    if cookbooks[j][i]>tmaterial[i]:\n",
    "                        meet=False\n",
    "                        break\n",
    "                    tmaterial[i]-=cookbooks[j][i]\n",
    "                if not meet:\n",
    "                    continue\n",
    "                csu,ccul=su,cul\n",
    "                csu+=attribute[j][0]\n",
    "                ccul+=+attribute[j][1]\n",
    "                if ccul>=limit: ### 前序更新\n",
    "                    self.ans=max(self.ans,csu)\n",
    "                getValue(tmaterial,j+1,csu,ccul)\n",
    "            #     res=max(res,attribute[x][0]+getValue(material,i+1,csu,ccul))\n",
    "            # return su+res if cul>=limit else 0\n",
    "        # return getValue(materials,0,0,0)\n",
    "        getValue(materials,0,0,0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        max_x = -1\n",
    "\n",
    "        def dfs(i, curr_x, curr_y, curr_materials):\n",
    "            nonlocal max_x\n",
    "            if i >= len(cookbooks):\n",
    "                return\n",
    "            \n",
    "            use_i = True\n",
    "            new_materials = curr_materials.copy()\n",
    "            for j in range(len(curr_materials)):\n",
    "                new_materials[j] -= cookbooks[i][j]\n",
    "                if new_materials[j] < 0:\n",
    "                    use_i = False\n",
    "                    break\n",
    "            \n",
    "            if use_i:\n",
    "                if curr_y + attribute[i][1] >= limit:\n",
    "                    max_x = max(max_x, curr_x + attribute[i][0])\n",
    "                dfs(i + 1, curr_x + attribute[i][0], curr_y + attribute[i][1], new_materials)\n",
    "            \n",
    "            dfs(i + 1, curr_x, curr_y, curr_materials)\n",
    "\n",
    "        dfs(0, 0, 0, materials)\n",
    "        return max_x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "\n",
    "        def dfs(ma, i, sums, beauty):\n",
    "            if i == n:\n",
    "                if sums >= limit:\n",
    "                    return beauty \n",
    "                else:\n",
    "                    return -1\n",
    "            ans = -1\n",
    "\n",
    "            nxt_ma = [0] * len(ma)\n",
    "            flag = 1\n",
    "            for j in range(len(ma)):\n",
    "                nxt_ma[j] = ma[j] - cookbooks[i][j] \n",
    "                if nxt_ma[j] < 0:\n",
    "                    flag = 0 \n",
    "            if flag:\n",
    "                ans = max(ans, dfs(nxt_ma,i+1, sums + attribute[i][1], beauty + attribute[i][0])) \n",
    "            ans = max(ans, dfs(ma, i+1, sums, beauty)) \n",
    "\n",
    "            return ans \n",
    "        n = len(cookbooks)\n",
    "\n",
    "        ans = dfs(materials, 0, 0, 0)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        ans = -1\n",
    "        for k in range(len(cookbooks)):\n",
    "            temp =  materials.copy()\n",
    "            x,y = 0,0\n",
    "            for i in range(k,len(cookbooks)):\n",
    "                make  = True\n",
    "                for j in range(len(cookbooks[i])):\n",
    "                    if temp[j]<cookbooks[i][j]:\n",
    "                        make  = False\n",
    "                        break\n",
    "                if make:\n",
    "                    for j in range(len(materials)):\n",
    "                        temp[j]-=cookbooks[i][j]\n",
    "                    x+=attribute[i][0]\n",
    "                    y+=attribute[i][1]\n",
    "            if y>=limit:\n",
    "                ans = max(ans,x)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]],\n",
    "                    limit: int) -> int:\n",
    "        ans = -1\n",
    "        n = len(cookbooks)\n",
    "        m = len(materials)\n",
    "        mw = 0\n",
    "        bf = 0\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            nonlocal mw\n",
    "            nonlocal bf\n",
    "            if i == n:\n",
    "                return\n",
    "            if all(cookbooks[i][j] <= materials[j] for j in range(m)):\n",
    "                for j in range(m):\n",
    "                    materials[j] -= cookbooks[i][j]\n",
    "                mw += attribute[i][0]\n",
    "                bf += attribute[i][1]\n",
    "                if bf >= limit:\n",
    "                    ans = max(ans, mw)\n",
    "                dfs(i + 1)\n",
    "                bf -= attribute[i][1]\n",
    "                mw -= attribute[i][0]\n",
    "                for j in range(m):\n",
    "                    materials[j] += cookbooks[i][j]\n",
    "            dfs(i + 1)\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]],\n",
    "                    limit: int) -> int:\n",
    "        index_attr = self.getAllSunset(attribute, limit)\n",
    "        index_new_attr = []\n",
    "        for index in index_attr:\n",
    "            # print(index)\n",
    "            sum_mater_0 = 0\n",
    "            sum_mater_1 = 0\n",
    "            sum_mater_2 = 0\n",
    "            sum_mater_3 = 0\n",
    "            sum_mater_4 = 0\n",
    "            for j in index:\n",
    "                sum_mater_0 += cookbooks[j][0]\n",
    "                sum_mater_1 += cookbooks[j][1]\n",
    "                sum_mater_2 += cookbooks[j][2]\n",
    "                sum_mater_3 += cookbooks[j][3]\n",
    "                sum_mater_4 += cookbooks[j][4]\n",
    "            # print(sum_mater_0)\n",
    "            if sum_mater_0 <= materials[0] and sum_mater_1 <= materials[1] and sum_mater_2 <= materials[\n",
    "                2] and sum_mater_3 <= materials[3] and sum_mater_4 <= materials[4]:\n",
    "                index_new_attr.append(index)\n",
    "        # print(index_new_attr)\n",
    "\n",
    "        if len(index_new_attr) == 0:\n",
    "            return -1\n",
    "\n",
    "        max_attr_x = 0\n",
    "        for index in index_new_attr:\n",
    "            sum_attr_x = 0\n",
    "            for i in index:\n",
    "                sum_attr_x += attribute[i][0]\n",
    "            max_attr_x = max(max_attr_x, sum_attr_x)\n",
    "        # print(max_attr_x)\n",
    "        return max_attr_x\n",
    "\n",
    "    def getAllSunset(self, attribute: List[List[int]], limit: int) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        index_res = [[]]\n",
    "        for j, attr in enumerate(attribute):\n",
    "            res += [i + [attr] for i in res]\n",
    "            index_res += [i + [j] for i in index_res]\n",
    "        # print(res)\n",
    "        index_new_res = []\n",
    "        for i, attr in enumerate(res):\n",
    "            temp_sum_attr = 0\n",
    "            for j in range(len(attr)):\n",
    "                temp_sum_attr += attr[j][1]\n",
    "            if temp_sum_attr >= limit:\n",
    "                index_new_res.append(index_res[i])\n",
    "        # print(index_new_res)\n",
    "        return index_new_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # class Solution:\n",
    "# #     def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "# #         m,n=len(materials),len(cookbooks)\n",
    "# #         # self.ans=0\n",
    "# #         def getValue(material,x,su,cul):\n",
    "# #             if x==n:return 0\n",
    "# #             if x>0:\n",
    "# #                 for i in range(m):\n",
    "# #                     if cookbooks[x][i]>material[i]:\n",
    "# #                         return su if cul>=limit else 0\n",
    "# #                     material[i]-=cookbooks[x][i]\n",
    "# #                 su+=attribute[x][0]\n",
    "# #                 cul+=attribute[x][1]\n",
    "# #             res=0\n",
    "# #             for i in range(x,n):\n",
    "# #                 res=max(res,attribute[i][0]+getValue(material,i+1,su,cul))\n",
    "# #             return su+res\n",
    "# #         return getValue(materials,0,0,0)\n",
    "\n",
    "# # class Solution:\n",
    "# #     def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "# #         m,n=len(materials),len(cookbooks)\n",
    "# #         # self.ans=0\n",
    "# #         def getValue(material,x,su,cul):\n",
    "# #             res=0\n",
    "# #             for i in range(x,n):\n",
    "# #                 meet=True\n",
    "# #                 for i in range(m):\n",
    "# #                     if cookbooks[x][i]>material[i]:\n",
    "# #                         meet=False\n",
    "# #                         break\n",
    "# #                     material[i]-=cookbooks[x][i]\n",
    "# #                 if not meet:\n",
    "# #                     continue\n",
    "# #                 csu,ccul=su,cul\n",
    "# #                 csu+=attribute[x][0]\n",
    "# #                 ccul+=+attribute[x][1]\n",
    "# #                 res=max(res,attribute[x][0]+getValue(material,i+1,csu,ccul))\n",
    "# #             return su+res if cul>=limit else 0\n",
    "# #         return getValue(materials,0,0,0)\n",
    "\n",
    "# # my：前序DFS\n",
    "# class Solution:\n",
    "#     def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "#         m,n=len(materials),len(cookbooks)\n",
    "#         self.ans=-1 ### 全局变量更新\n",
    "#         def getValue(material,x,su,cul):\n",
    "#             if cul>=limit:\n",
    "#                 self.ans=max(self.ans,su)\n",
    "#             for j in range(x,n):\n",
    "#                 meet=True\n",
    "#                 tmaterial=material[:]### 千万注意列表形式的更新（两列表是否共用内存地址）\n",
    "#                 for i in range(m):\n",
    "#                     if cookbooks[j][i]>tmaterial[i]:\n",
    "#                         meet=False\n",
    "#                         break\n",
    "#                     tmaterial[i]-=cookbooks[j][i]\n",
    "#                 if not meet:\n",
    "#                     continue\n",
    "#                 csu,ccul=su,cul\n",
    "#                 csu+=attribute[j][0]\n",
    "#                 ccul+=+attribute[j][1]\n",
    "#                 if ccul>=limit: ### 前序更新\n",
    "#                     self.ans=max(self.ans,csu)\n",
    "#                 getValue(tmaterial,j+1,csu,ccul)\n",
    "#             #     res=max(res,attribute[x][0]+getValue(material,i+1,csu,ccul))\n",
    "#             # return su+res if cul>=limit else 0\n",
    "#         # return getValue(materials,0,0,0)\n",
    "#         getValue(materials,0,0,0)\n",
    "#         return self.ans\n",
    "\n",
    "# ### 网：作者：Robot123---回溯\n",
    "# # 链接：https://leetcode.cn/problems/UEcfPD/\n",
    "# class Solution:\n",
    "#     def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "#         def has_materials(materials):\n",
    "#             for material in materials:\n",
    "#                 if material < 0:\n",
    "#                     return False\n",
    "#             return True\n",
    "        \n",
    "#         def can_cookbooks(materials, cookbook):\n",
    "#             materials = [materials[i] - cookbook[i] for i in range(num_material)]\n",
    "#             return materials\n",
    "\n",
    "        \n",
    "#         def back_trace(materials, x, y, deep):\n",
    "#             if y >= limit:\n",
    "#                     ans.append(x)\n",
    "#             if deep < num_attribute:\n",
    "#                 back_trace(materials[:], x, y, deep + 1)\n",
    "#                 materials =  can_cookbooks(materials, cookbooks[deep])\n",
    "#                 if has_materials(materials):\n",
    "#                     back_trace(materials[:], x+attribute[deep][0], y+attribute[deep][1], deep + 1)\n",
    "#         ans = [-1]\n",
    "#         num_attribute = len(attribute)\n",
    "#         num_material = len(materials)\n",
    "#         back_trace(materials, 0, 0, 0)\n",
    "#         return max(ans)\n",
    "\n",
    "\n",
    "### 网2：回溯作者：danspace\n",
    "# 链接：https://leetcode.cn/problems/UEcfPD/\n",
    "class Solution:\n",
    "\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "\n",
    "        # 菜谱数量\n",
    "\n",
    "        n = len(cookbooks)\n",
    "\n",
    "        # 初始化结果\n",
    "\n",
    "        res = -1\n",
    "\n",
    "        # 已做的菜谱\n",
    "\n",
    "        done = [False]*n \n",
    "\n",
    "        \n",
    "\n",
    "        def dfs(materials, sum_x, sum_y):\n",
    "\n",
    "            \"\"\"遍历菜谱，将可获得的美味度放入结果列表\n",
    "\n",
    "\n",
    "\n",
    "            Args:\n",
    "\n",
    "                materials (list): 当前食材\n",
    "\n",
    "                sum_x (int): 累计美味度 x\n",
    "\n",
    "                sum_y (int): 累计美味度 y\n",
    "\n",
    "            \"\"\"    \n",
    "\n",
    "            nonlocal res\n",
    "\n",
    "            if sum_y >= limit:\n",
    "\n",
    "                res = max(res, sum_x)\n",
    "\n",
    "            \n",
    "\n",
    "            for i in range(n):\n",
    "\n",
    "                # 如果菜已做，则不能重复做\n",
    "\n",
    "                if done[i]:\n",
    "\n",
    "                    continue \n",
    "\n",
    "                # 检查能否做第i个菜\n",
    "\n",
    "                check = True \n",
    "\n",
    "                for j in range(len(materials)):\n",
    "\n",
    "                    if materials[j] < cookbooks[i][j]:\n",
    "\n",
    "                        check = False \n",
    "\n",
    "                        break \n",
    "\n",
    "                if check:\n",
    "\n",
    "                    # 做第i个菜\n",
    "\n",
    "                    for j in range(len(materials)):\n",
    "\n",
    "                        materials[j] -= cookbooks[i][j]\n",
    "\n",
    "                    # 更新已做的菜谱\n",
    "\n",
    "                    done[i] = True\n",
    "\n",
    "                    # 继续用剩余的材料做菜\n",
    "\n",
    "                    dfs(materials, sum_x + attribute[i][0], sum_y + attribute[i][1])\n",
    "\n",
    "                    # 还原\n",
    "\n",
    "                    done[i] = False \n",
    "\n",
    "                    for j in range(len(materials)):\n",
    "\n",
    "                        materials[j] += cookbooks[i][j]\n",
    "\n",
    "                    \n",
    "\n",
    "        dfs(materials, 0, 0)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        n=len(cookbooks)\n",
    "        target=-1\n",
    "        for i in range(1,1<<n):\n",
    "            hungry=0\n",
    "            delicous=0\n",
    "            s=materials \n",
    "            for j in range(0,n):\n",
    "                if i&(1<<j)!=0:\n",
    "                    hungry+=attribute[j][1]\n",
    "                    delicous+=attribute[j][0]\n",
    "                    s=[x-y for x,y in zip(s,cookbooks[j])]\n",
    "            if hungry>=limit and min(s)>=0:\n",
    "                target=max(delicous,target)\n",
    "        return target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        n=len(cookbooks)\n",
    "        ans=-1\n",
    "        for i in range(1<<n):\n",
    "            cook=[0]*5\n",
    "            attr=[0,0]\n",
    "            for j in range(n):\n",
    "                if i & (1<<j):\n",
    "                    # 方案i需要做cook[j],获得属性attr[j]\n",
    "                    for k in range(5):\n",
    "                        cook[k]+=cookbooks[j][k]\n",
    "                    attr[0]+=attribute[j][0]\n",
    "                    attr[1]+=attribute[j][1]\n",
    "            # 状态总结sum\n",
    "            for k in range(5):\n",
    "                if cook[k]>materials[k]:\n",
    "                    break\n",
    "            else:\n",
    "                if attr[1]>=limit:\n",
    "                    ans=max(ans,attr[0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        biggest = 0\n",
    "\n",
    "        def find(cookbooks, attribute, materials, delicious, full):\n",
    "                nonlocal biggest\n",
    "                nonlocal limit\n",
    "                for i in range(len(cookbooks)):\n",
    "                    tmp = copy.deepcopy(materials)\n",
    "                    mark = 0\n",
    "                    for j in range(len(materials)):\n",
    "                        if materials[j] - cookbooks[i][j] < 0:\n",
    "                            mark = 1\n",
    "                            break\n",
    "                        tmp[j] = materials[j] - cookbooks[i][j]\n",
    "\n",
    "                    if mark == 0:\n",
    "                        if full + attribute[i][1] >= limit:\n",
    "                            biggest = max(biggest, delicious + attribute[i][0])\n",
    "                        find(cookbooks[:i] + cookbooks[i + 1:], attribute[:i] + attribute[i + 1:], tmp,delicious + attribute[i][0], full + attribute[i][1])\n",
    "\n",
    "        find(cookbooks, attribute, materials, 0, 0)\n",
    "        if biggest==0:\n",
    "            return -1\n",
    "        return biggest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        def f(index,restmaterials,cookbooks,attribute,curbfg,curmwg,ans,limit):\n",
    "            for i in restmaterials:\n",
    "                if i<0:\n",
    "                    return False\n",
    "            if index==len(cookbooks):\n",
    "                if curbfg>=limit:\n",
    "                    ans.append(curmwg)\n",
    "                return True\n",
    "            f(index+1,restmaterials.copy(),cookbooks,attribute,curbfg,curmwg,ans,limit)\n",
    "            currest=restmaterials.copy()\n",
    "            for j in range(len(materials)):\n",
    "                currest[j]-=cookbooks[index][j]\n",
    "            f(index+1,currest,cookbooks,attribute,curbfg+attribute[index][1],curmwg+attribute[index][0],ans,limit)\n",
    "        ans=[-1]\n",
    "        f(0,materials,cookbooks,attribute,0,0,ans,limit)\n",
    "        return max(ans)\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        \"\"\"先弄子集，再剪枝\"\"\"\n",
    "        # 计算美味度\n",
    "        def calcu_dili(li):\n",
    "            dili=0\n",
    "            for i in li:\n",
    "                dili+=attribute[i][0]\n",
    "            return dili\n",
    "        def calcu_limi(li):\n",
    "            limi_sum=0\n",
    "            for i in li:\n",
    "                limi_sum+=attribute[i][1]\n",
    "            return limi_sum>=limit\n",
    "        def is_matr_enough(li):\n",
    "            if not li:return True\n",
    "            cooks=[cookbooks[i] for i in li]\n",
    "            maters_sums=[sum(i) for i in list(zip(*cooks))]\n",
    "            diff=[materials[i]-maters_sums[i] for i in range(0,len(materials))]\n",
    "            # print(f\"cooks:{cooks}\")\n",
    "            # print(f\"diff:{diff}\")\n",
    "            return all([i>=0 for i in diff])\n",
    "        \n",
    "        # 计算backtracking\n",
    "        res,path=[],[]\n",
    "        def backtracking(cur):\n",
    "            # 放入\n",
    "            if is_matr_enough(path):\n",
    "                res.append(path[:])\n",
    "            else:\n",
    "                return\n",
    "            for i in range(cur,len(cookbooks)):\n",
    "                path.append(i)\n",
    "                backtracking(i+1)\n",
    "                path.pop()\n",
    "        backtracking(0)\n",
    "        print(res)\n",
    "        # 计算每个美味程度\n",
    "        max_dili=0\n",
    "        for li in res:\n",
    "            if calcu_limi(li):\n",
    "                max_dili=max(max_dili,calcu_dili(li))\n",
    "        return max_dili if max_dili>0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        coun=-1\n",
    "        l1=len(cookbooks)\n",
    "        l2=len(materials)\n",
    "        for i in range(2**l1):\n",
    "            k=0\n",
    "            p=list(materials)\n",
    "            full=0\n",
    "            taste=0\n",
    "            t=bin(i)[2:].zfill(l1)\n",
    "            for x in range(l1):\n",
    "                if int(t[x])==1:\n",
    "                    full+=attribute[x][1]\n",
    "                    taste+=attribute[x][0]\n",
    "                    for j in range(l2):\n",
    "                        if not cookbooks[x][j]>p[j]:\n",
    "                            p[j]-=cookbooks[x][j]\n",
    "                        else:\n",
    "                            k=1\n",
    "                            break\n",
    "                    if k==1:\n",
    "                        break\n",
    "            if full>=limit and k!=1:\n",
    "                coun=max(coun,taste)\n",
    "        return coun\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        ans=[]\n",
    "        n=len(cookbooks)\n",
    "        lastmt=materials\n",
    "        delicious=0\n",
    "        full=0\n",
    "        def backtrack(index):\n",
    "            nonlocal lastmt,delicious,full\n",
    "            for i in range(index,n):\n",
    "                lastmt=[lastmt[a]-cookbooks[i][a] for a in range(5)]\n",
    "                if min(lastmt)<0:\n",
    "                    if full>=limit:\n",
    "                        ans.append(delicious)\n",
    "                    lastmt=[lastmt[a]+cookbooks[i][a] for a in range(5)]\n",
    "                    continue\n",
    "                else:\n",
    "                    delicious+=attribute[i][0]\n",
    "                    full+=attribute[i][1]\n",
    "                    if full>=limit:\n",
    "                        ans.append(delicious) \n",
    "                    if i==n-1:\n",
    "                        delicious-=attribute[i][0]\n",
    "                        full-=attribute[i][1]\n",
    "                        lastmt=[lastmt[a]+cookbooks[i][a] for a in range(5)]\n",
    "                        continue        \n",
    "                    backtrack(i+1)\n",
    "                    delicious-=attribute[i][0]\n",
    "                    full-=attribute[i][1]\n",
    "                    lastmt=[lastmt[a]+cookbooks[i][a] for a in range(5)]\n",
    "        backtrack(0)\n",
    "        return -1 if len(ans)==0 else max(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials, cookbooks, attribute, limit):\n",
    "        max_delicious = 0\n",
    "        hungry = 0\n",
    "        delicious = 0\n",
    "        materials_list = materials\n",
    "        i=0\n",
    "        j=1\n",
    "        while j <= len(cookbooks):\n",
    "            materials = [x - y for x, y in zip(materials, cookbooks[i])]\n",
    "            flag = False\n",
    "            for m in materials:\n",
    "                if m < 0:\n",
    "                    flag = True\n",
    "                    break\n",
    "            if flag:\n",
    "                if i == j-1:\n",
    "                    i = j\n",
    "                    j = j+1\n",
    "                    hungry = 0\n",
    "                    delicious = 0\n",
    "                    materials = materials_list\n",
    "                else:\n",
    "                    # if materials != materials_list:\n",
    "                    if hungry >= limit:\n",
    "                        if delicious > max_delicious:\n",
    "                            max_delicious = delicious\n",
    "                    # materials = materials_list\n",
    "                    if i == len(cookbooks)-1:\n",
    "                        materials = materials_list\n",
    "                        i = j\n",
    "                        j = j+1\n",
    "                        hungry = 0\n",
    "                        delicious = 0\n",
    "                    else:\n",
    "                        materials = [x + y for x, y in zip(materials, cookbooks[i])]\n",
    "                        i += 1\n",
    "            else:\n",
    "                hungry = hungry + attribute[i][1]\n",
    "                delicious = delicious + attribute[i][0]\n",
    "                if attribute[i][1] >= limit:\n",
    "                    if attribute[i][0] > max_delicious:\n",
    "                        max_delicious = attribute[i][0]\n",
    "                if i < len(cookbooks)-1:\n",
    "                    i += 1\n",
    "\n",
    "        if max_delicious == 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return max_delicious\n",
    "\n",
    "\n",
    "# materials = [4,20,16,17,14]\n",
    "# cookbooks = [[3,1,6,12,18],[12,7,17,19,16],[18,4,7,8,0],[18,9,20,16,4],[17,15,4,7,15],[2,8,9,3,13],[20,12,0,7,17],[3,2,7,5,5]]\n",
    "# attribute = [[13,4],[7,18],[3,11],[6,20],[9,0],[13,16],[18,3],[2,5]]\n",
    "# limit = 5\n",
    "\n",
    "# materials = [10,10,10,10,10]\n",
    "# cookbooks = [[1,1,1,1,1],[3,3,3,3,3],[10,10,10,10,10]]\n",
    "# attribute = [[5,5],[6,6],[10,10]]\n",
    "# limit = 1\n",
    "\n",
    "# materials = [13,17,19,17,5]\n",
    "# cookbooks = [[17,0,8,0,9],[7,11,0,1,4],[1,20,2,11,17],[11,14,6,12,18],[4,18,1,11,2],[17,7,0,6,17],[1,6,8,2,1],[14,14,12,16,10]]\n",
    "# attribute = [[19,1],[13,11],[3,15],[6,2],[19,19],[13,17],[20,17],[17,19]]\n",
    "# limit = 8\n",
    "\n",
    " \n",
    "# materials = [3,2,4,1,2]\n",
    "# cookbooks = [[1,1,0,1,2],[2,1,4,0,0],[3,2,4,1,0]]\n",
    "# attribute = [[3,2],[2,4],[7,6]]\n",
    "# limit = 5\n",
    "\n",
    "# materials =[9,16,2,16,3]\n",
    "# cookbooks =\t[[10,17,13,9,7],[8,3,12,10,0],[12,4,6,19,3],[2,3,1,5,0]]\n",
    "# attribute =\t[[19,6],[0,3],[11,7],[19,15]]\n",
    "# limit = 17\n",
    "\n",
    "# a = Solution()\n",
    "# print(a.perfectMenu(materials, cookbooks, attribute, limit))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        dp = [[0, 0, [0]*len(materials)] for _ in range(len(cookbooks) + 1)]\n",
    "        result = -1\n",
    "        # [print(x) for x in dp]\n",
    "        for i in range(1, len(cookbooks) + 1):\n",
    "            # print('-'*10, i, cookbooks[i-1], attribute[i-1])\n",
    "            flag = True\n",
    "            for num1, num2 in zip(materials, cookbooks[i-1]):\n",
    "                if num2 > num1:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag is False:\n",
    "                dp[i][0], dp[i][1], dp[i][2] = dp[i-1][0], dp[i-1][1], dp[i-1][2]\n",
    "                continue\n",
    "            rest_materials = [x-y for x, y in zip(materials, cookbooks[i-1])]\n",
    "            flag = True\n",
    "            for j in range(i-1, 0, -1):\n",
    "                # print(10.12, rest_materials, dp[j][2])\n",
    "                for num1, num2 in zip(rest_materials, dp[j][2]):\n",
    "                    if num1 < num2:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    dp[i][0] = attribute[i-1][0] + dp[j][0]\n",
    "                    dp[i][1] = attribute[i-1][1] + dp[j][1]\n",
    "                    dp[i][2] = [x+y for x, y in zip(cookbooks[i-1], dp[j][2])]\n",
    "                    print(10.2, dp)\n",
    "                    break\n",
    "            # print(10.21, flag, rest_materials)\n",
    "            if dp[i][1] < 1:\n",
    "                dp[i][0] = 0\n",
    "            flag = True\n",
    "            for x, y in zip(materials, cookbooks[i - 1]):\n",
    "                if x < y:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                if dp[i][0] < attribute[i-1][0]:\n",
    "                    dp[i][0] = attribute[i-1][0]\n",
    "                    dp[i][1] = attribute[i-1][1]\n",
    "                    dp[i][2] = cookbooks[i-1]\n",
    "                    print(10.3, dp)\n",
    "            if result < dp[i][0] and dp[i][1] >= limit:\n",
    "                result = dp[i][0]\n",
    "            # [print(x) for x in dp]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        subsets = []\n",
    "        path = []\n",
    "        maxy = -1\n",
    "        nums = [i for i in range(len(attribute))]  # 存储索引\n",
    "        def subset(nums):\n",
    "            nonlocal maxy\n",
    "            print(path)\n",
    "            if judge(path):\n",
    "                maxy = max(maxy,sum(attribute[i][0] for i in path))\n",
    "                print(path,maxy)\n",
    "            for i in range(len(nums)):\n",
    "                path.append(nums[i])\n",
    "                subset(nums[i+1:])\n",
    "                path.pop()\n",
    "        # 根据索引判断是否合法\n",
    "        def judge(path):\n",
    "            totalx = 0\n",
    "            tmp = [0]*len(materials)\n",
    "            for i in path:\n",
    "                totalx += attribute[i][1]\n",
    "                for j in range(len(tmp)):\n",
    "                    tmp[j] += cookbooks[i][j]\n",
    "            if totalx < limit:\n",
    "                return False\n",
    "            for i in range(len(tmp)):\n",
    "                if tmp[i] > materials[i]:\n",
    "                    return False\n",
    "            return True\n",
    "            \n",
    "        subset(nums)\n",
    "        return maxy\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        # 当前处理第i种料理, 返回美味度x\n",
    "        def f(i, x, y, m):\n",
    "            if i == len(cookbooks):\n",
    "                if y >= limit:\n",
    "                    res.append(x)\n",
    "                return\n",
    "            # 如果剩余食材能够满足第i种料理, 那么选i\n",
    "            for a, b in zip(m, cookbooks[i]):\n",
    "                if a < b:\n",
    "                    break\n",
    "            else:\n",
    "                newM = [a-b for a, b in zip(m, cookbooks[i])]\n",
    "                xx, yy = attribute[i]\n",
    "                f(i+1,x+xx,y+yy,newM)\n",
    "            # 不选i\n",
    "            f(i+1,x,y,m)\n",
    "\n",
    "        res = [-1]\n",
    "        n = len(cookbooks)\n",
    "        f(0,0,0,materials)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtracking(self,materials,cookbooks,attribute,hunger,spiritual,limit,startIndex):\n",
    "        temp=True#是否返回结果\n",
    "        for x in range(startIndex,len(cookbooks)):\n",
    "            for y in range(5):\n",
    "                if materials[y]<cookbooks[x][y]:\n",
    "                    break\n",
    "            if y==4 and materials[y]>=cookbooks[x][y]:\n",
    "                temp=False\n",
    "            if not temp:\n",
    "                break\n",
    "\n",
    "\n",
    "        if startIndex==len(cookbooks) or temp:\n",
    "            if hunger>=limit:\n",
    "                self.maxspiritual=max(self.maxspiritual,spiritual)\n",
    "            return\n",
    "        \n",
    "        for i in range(startIndex,len(cookbooks)):\n",
    "            for j in range(5):\n",
    "                if materials[j]<cookbooks[i][j]:\n",
    "                    break\n",
    "            if j==4 and materials[j]>=cookbooks[i][j]:\n",
    "                materials=[materials[j]-cookbooks[i][j] for j in range(5)]\n",
    "                self.backtracking(materials,cookbooks,attribute,hunger+attribute[i][1],spiritual+attribute[i][0],limit,i+1)\n",
    "                materials=[materials[j]+cookbooks[i][j] for j in range(5)]\n",
    "\n",
    "\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        self.maxspiritual=0\n",
    "        self.backtracking(materials,cookbooks,attribute,0,0,limit,0)\n",
    "        return self.maxspiritual if self.maxspiritual!=0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        num = len(cookbooks)\n",
    "        max_delicious = [-1]\n",
    "        def dfs(temp_materials, nextcook, temp_hunger, temp_delicious, max_delicious):\n",
    "            if temp_hunger >= limit:\n",
    "                max_delicious[0] = max(max_delicious[0], temp_delicious)\n",
    "            for i in range(nextcook, num):\n",
    "                flag = 0\n",
    "                for j in range(5):\n",
    "                    if temp_materials[j] < cookbooks[i][j]:\n",
    "                        flag = 1\n",
    "                if flag == 1:\n",
    "                    continue\n",
    "                for j in range(5):\n",
    "                    temp_materials[j] -= cookbooks[i][j]\n",
    "                temp_delicious += attribute[i][0]\n",
    "                temp_hunger += attribute[i][1]\n",
    "                dfs(temp_materials, i + 1, temp_hunger, temp_delicious, max_delicious)\n",
    "                temp_delicious -= attribute[i][0]\n",
    "                temp_hunger -= attribute[i][1]\n",
    "                for j in range(5):\n",
    "                    temp_materials[j] += cookbooks[i][j]\n",
    "        dfs(materials, 0, 0, 0, max_delicious)\n",
    "        return max_delicious[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        ans=-1\n",
    "        n=len(materials)\n",
    "        vis=[0]*len(cookbooks)\n",
    "        def dfs(m,cookbooks,s,h):\n",
    "            nonlocal ans\n",
    "            if h>=limit :\n",
    "                ans=max(s,ans)\n",
    "            for j in range(len(cookbooks)):\n",
    "                newm=m\n",
    "                f=0\n",
    "                if vis[j]!=0:\n",
    "                    continue\n",
    "                for i in range(n):\n",
    "                    if newm[i]<cookbooks[j][i]:\n",
    "                        f=1\n",
    "                        break\n",
    "                if f==0:\n",
    "                    for i in range(n):\n",
    "                        newm[i]=newm[i]-cookbooks[j][i]\n",
    "                    vis[j]=1\n",
    "                    news=s+attribute[j][0]\n",
    "                    newh=h+attribute[j][1]\n",
    "                    dfs(newm,cookbooks,news,newh)\n",
    "                    vis[j]=1\n",
    "                    for i in range(n):\n",
    "                        newm[i]=newm[i]+cookbooks[j][i]\n",
    "        dfs(materials,cookbooks,0,0)\n",
    "        return ans\n",
    "                    \n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        n = len(cookbooks)\n",
    "        memory = {}\n",
    "        ans = -1\n",
    "        def dfs(state, materials, limit, good):\n",
    "            if state in memory:\n",
    "                return\n",
    "            memory[state] = (limit, good)\n",
    "            for i in range(n):\n",
    "                if state & (1<<i) == 0:\n",
    "                    left_materials = [materials[j]-cookbooks[i][j] for j in range(len(materials))]\n",
    "                    if all([x >= 0 for x in left_materials]):\n",
    "                        dfs(state^(1<<i), left_materials, limit-attribute[i][1], good+attribute[i][0])\n",
    "        dfs(0, materials, limit, 0)\n",
    "        for key in memory:\n",
    "            if memory[key][0] <= 0:\n",
    "                ans = max(ans, memory[key][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        ans = -1\n",
    "        for k in range(len(cookbooks)):\n",
    "            temp =  materials.copy()\n",
    "            x,y = 0,0\n",
    "            for i in range(k,len(cookbooks)):\n",
    "                make  = True\n",
    "                for j in range(len(cookbooks[i])):\n",
    "                    if temp[j]<cookbooks[i][j]:\n",
    "                        make  = False\n",
    "                        break\n",
    "                if make:\n",
    "                    for j in range(len(materials)):\n",
    "                        temp[j]-=cookbooks[i][j]\n",
    "                    x+=attribute[i][0]\n",
    "                    y+=attribute[i][1]\n",
    "            if y>=limit:\n",
    "                ans = max(ans,x)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:\n",
    "        global final\n",
    "        final = -1\n",
    "        def dfs(leave, need, curDelicious, p):\n",
    "          global final\n",
    "          if need <= 0:\n",
    "              if final < curDelicious:\n",
    "                  final = curDelicious\n",
    "\n",
    "          for i in range(p, len(cookbooks)):\n",
    "                success = True\n",
    "                temp = [0] * len(materials)\n",
    "                for j in range(len(materials)):\n",
    "                    temp[j] = leave[j] - cookbooks[i][j]\n",
    "                    if temp[j] >= 0:\n",
    "                        continue\n",
    "                    else:\n",
    "                        success = False\n",
    "                        break\n",
    "            # 第i种食谱可以做，那么就先做，做完后再去做其他食谱\n",
    "                if success:\n",
    "                    dfs(temp, need - attribute[i][-1], curDelicious + attribute[i][0], i+1)\n",
    "            # 还要遍历不做这种食谱的情况\n",
    "                else:\n",
    "                    dfs(leave, need, curDelicious, i+1)\n",
    "\n",
    "        dfs(materials, limit, 0, 0)\n",
    "        return final\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
